package com.ly.algorithm.DataStructures.sort;
import	java.util.Date;

import java.util.Random;

/**
 * @Classname MergetSort
 * @Description TODO
 * @Date 2020/4/24 18:47
 * @Author 冷心影翼
 */
public class MergetSort {

    public static void main(String[] args) {
//        int[] arr = {1.txt,4,33,22,32,21,34,-2,34,7};

        int[] arr = new int[8000000];
        int temp[] = new int[arr.length];
        Random random = new Random();
        for(int i=0;i<8000000;i++) {
            arr[i] =  random.nextInt(8000000);
        }
//        System.out.println(Arrays.toString(arr));
        Date date1 = new Date();
        mergeSort(arr,0,arr.length-1,temp);

        Date date2 = new Date();
//        System.out.println(Arrays.toString(arr));
        System.out.println(date2.getTime()-date1.getTime());
    }

    public static void mergeSort(int[] arr,int left,int right,int[] temp) {
        if(left<right) {
            int mid = (left+right)/2;
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid+1,right, temp);
            merge(arr,left,mid,right,temp);
        }
    }

    public static void merge(int[] arr,int left,int mid,int right,int[] temp) {
        int i = left;
        int j= mid + 1;
        int t = 0;
        while (i<=mid && j<=right) {
            if(arr[i]<=arr[j]) {
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }

        while (i<=mid) {
            temp[t++] = arr[i++];
        }

        while (j<=right) {
            temp[t++] = arr[j++];
        }

        t=0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }
    }
}
